/*四边形不等式
* 1.四边形不等式
    定义方式1:若 a≤b≤c≤d，而且 W(a,d)+W(b,c)≥W(a,c)+W(b,d)，则称函数W(x,y)满足四边形不等式
    (单调性)        不等号成立:W(x, y)=(x+y)^2
    定义方式2.对于 ∀a<b∈Z+，都有 a<a+1≤b<b+1。这里分别把a,a+1,b,b+1视为刚刚的a,b,c,d，如果W(a,b+1)+W(a+1,b)≥W(a,b)+W(a+1,b+1)，那么W满足四边形不等式
    (函数本身具有四边形不等式关系)

* 2.dp转移方程:f[i]=min(0≤j<i)f[j]+V(j, i);
    如果V(j, i)满足四边形不等式，那么f[i]的最优决策具有单调性
    即：如果p[i]表示f[i]取到的最优解的j，则p[i]单调不递减。
    如果q决策在i取到k的时候比他前面的所有决策都好，那么q在i'>k时仍然比他前面的所有决策更好
    因此决策p[]一定是单调的
    所以dp转移方程可以优化为f[i]=f[p[i]]+V(p[i], i);

    用单调队列维护
        对于每个i，我们将其插入队列中时，可以直接将所有比i差的决策都出队，直到i不比队头的决策更优，
        那么如果队头决策比i更优，则直接把队头元素后面的所有决策改成i
        否则我们可以在队头的 [l,r]中二分查找，找到一个位置pos ，使得pos前面的所有决策都比i更优，
        后面决策i更优，然后将pos后面的所有决策都改为i
        同时，我们不需要在在队列中保存 1∼i 的部分，我们可以直接将其出队
        这样我们在计算fi的时候，直接取队头元素，就是最优决策

* 本题:
    状态转移方程: f[i][j]=min(i≤k<j)f[i][k]+f[k+1][j]+w[i][j]
                    f[i][i]=w[i][i]=0
    并且对于 a≤b≤c≤d，显然存在 w(a,d)≥w(b,c)，所有条件满足，则f满足二维四边形不等式
*/

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define DEBUG
inline int read()
{
	int x=0;char c=getchar();
	while (c<'0'||c>'9') c=getchar();
	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+c-48,c=getchar();
	return x;
}
inline void write(int x)
{
	if (x>=10) write(x/10);
	putchar(x%10+48);
}//快读快输
const int N=5010;

int n;
int a[N], s[N]; //原序列 前i个石头堆重量和
int f[N][N]; //f[i][j]将i~j合并的最小代价
int p[N][N]; //p[i][j]:f[i][j]的最优决策

void solve()
{
    n=read();
    for(int i=1; i<=n; i++)
    {
        a[i]=read();
        s[i]=s[i-1]+a[i];
    }
    memset(f, 0x3f, sizeof f);
    for(int i=1; i<=n; i++)
    {
        f[i][i]=0;
        p[i][i]=i;
    }

    //二维四边形不等式优化区间DP
    for(int l=n-1; l>=1; l--) //枚举左端点
        for(int r=l+1; r<=n; r++) //枚举右端点
            for(int k=p[l][r-1]; k<=p[l+1][r]; k++) //枚举决策点
            if(l<=k && k<r && f[l][k]+f[k+1][r]+s[r]-s[l-1]<f[l][r]) //决策点合法且更优
            {
                f[l][r]=f[l][k]+f[k+1][r]+s[r]-s[l-1];
                p[l][r]=k; //记录转移过来的决策点
            }
    write(f[1][n]); puts("");
}

signed main()
{
    #ifdef DEBUG
        freopen("./in.txt","r",stdin);
        freopen("./out.txt","w",stdout);
    #endif

    
    int T=1; //T=read();
    while(T--)
    {
        solve();
    }
    return 0;
}